package com.leetcode.test.linklist.doublePoint;

import com.leetcode.test.linklist.ListNode;
import org.junit.Assert;
import org.junit.Test;

import java.util.HashSet;
import java.util.Set;

/**
 * 环形表2
 * <p>
 * 官方解答：https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode/
 */
public class CycleII {

    @Test
    public void testA() {
//        输入：head = [3,2,0,-4], pos = 1
//        输出：true
//        解释：链表中有一个环，其尾部连接到第二个节点。
        ListNode node3  = new ListNode(3);
        ListNode node2  = new ListNode(2);
        ListNode node0  = new ListNode(0);
        ListNode node_4 = new ListNode(-4);

        node3.next = node2;
        node2.next = node0;
        node0.next = node_4;
        node_4.next = node2;

        ListNode result = detectCycle(node3);
        Assert.assertEquals(result, node2);
    }

    // Floyd 算法
//    public ListNode detectCycle(ListNode head) {
//
//    }

    // 哈希表解法
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set  = new HashSet<>();
        ListNode      node = head;

        while (node != null) {
            if (set.contains(node)) {
                // 入链的第一个节点
                return node;
            }
            set.add(node);
            node = node.next;
        }

        return null;
    }
}
